import collections
class Solution(object):
    def combinationSum4(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        n = len(nums)
        count = 0
        now = collections.defaultdict(int)
        for i in range(n):
            if nums[i] < target:
                now[nums[i]] += 1
            if nums[i] == target:
                count += 1
        while now:
            next_dict = collections.defaultdict(int)
            for val in now:
                for i in range(n):
                    if val + nums[i] < target:
                        next_dict[val + nums[i]] += now[val]
                    if val + nums[i] == target:
                        count += now[val]
            now = next_dict
        return count



data = Solution()
nums = [1, 2, 3]
target = 4
print(data.combinationSum4(nums, target))
